package alogrithm;

import java.util.Arrays;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/9 20:39
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] a = new int[]{1, 7, 5, 6, 4, 2, 3};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void heapSort(int[] a) {
        // 从最后一个子树的父节点开始处理, 直到根节点
        for (int i = a.length / 2 - 1; i >= 0; --i) {
            adjustHeap(a, i, a.length);
        }

        // 每次构造完一个堆后, 将堆顶的元素交换至数组最后一个, 实现排序
        for (int j = a.length - 1; j >= 0; j--) {
            int tmp = a[0];
            a[0] = a[j];
            a[j] = tmp;
            adjustHeap(a, 0, j);
        }
    }

    private static void adjustHeap(int[] a, int i, int j) { // 若判断时将判断的条件改成<,则实现的是降序排序
        int temp = a[i]; // 保存当前父节点的值
        for (int k = i * 2 + 1; k < j; k = k * 2 + 1) { // 循环处理该父节点下的所有子树
            if (k + 1 < j && a[k + 1] > a[k]) {
                k++; // 右孩子比左孩子大, 处理右孩子
            }
            if (a[k] > temp) { // 如果右孩子比父节点的值大, 交换两个结点的值
                a[i] = a[k];
                i = k;
            } else {
                break;
            }
        }
        a[i] = temp; // 将父节点的值,放在调整完后的结点上
    }


    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
